//给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != 
//k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 
//
// 你返回所有和为 0 且不重复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
//注意，输出的顺序和三元组的顺序并不重要。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,1]
//输出：[]
//解释：唯一可能的三元组和不为 0 。
// 
//
// 示例 3： 
//
// 
//输入：nums = [0,0,0]
//输出：[[0,0,0]]
//解释：唯一可能的三元组和为 0 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 3000 
// -10⁵ <= nums[i] <= 10⁵ 
// 
//
// Related Topics 数组 双指针 排序 👍 5945 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution15_暴力 {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Set<String> mark = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            List<int[]> tsList = twoSum(nums, i + 1, 0 - nums[i]);
            for (int[] ts : tsList) {
                // if (ts != null) {
                List<Integer> item = null;
                if (nums[i] <= ts[0]) {
                    item = Arrays.asList(nums[i], ts[0], ts[1]);
                } else if (nums[i] <= ts[1]) {
                    item = Arrays.asList(ts[0], nums[i], ts[1]);
                } else {
                    item = Arrays.asList(ts[0], ts[1], nums[i]);
                }
                String markKey = "" + item.get(0) + item.get(1) + item.get(2);
                if (mark.add(markKey) == true) {
                    ans.add(item);
                }
                // }
            }
        }

        return ans;
    }

    private List<int[]> twoSum(int[] nums, int begin, int target) {
        List<int[]> ans = new ArrayList<>();
        HashMap<Integer, Integer> tables = new HashMap<>();
        HashSet<Integer> mark = new HashSet();
        for (int i = begin; i < nums.length; i++) {
            if (mark.contains(nums[i])) continue;
            Integer diffNumIx = tables.get(target - nums[i]);
            if (diffNumIx != null) {
                int curr = nums[i];
                int diffNum = target - nums[i];
                int s = curr < diffNum ? curr : diffNum;
                int b = s == curr ? diffNum : curr;
                ans.add(new int[]{s, b});
                mark.add(s);
                mark.add(b);
            }
            tables.put(nums[i], i);
        }
        return ans;
    }
}

/**
 * 不排序, 去重方式简化 --fail
 */
class Solution15_Fail {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Set<Integer> mark = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (mark.add(nums[i]) == false) continue;
            List<int[]> tsList = twoSum(nums, i + 1, 0 - nums[i]); // 保证无重复解
            for (int[] ts : tsList) {
                ans.add(Arrays.asList(nums[i], ts[0], ts[1]));
            }
        }

        return ans;
    }

    private List<int[]> twoSum(int[] nums, int begin, int target) {
        List<int[]> ans = new ArrayList<>();
        HashMap<Integer, Integer> tables = new HashMap<>();
        HashSet<Integer> mark = new HashSet();
        for (int i = begin; i < nums.length; i++) {
            if (mark.contains(nums[i])) continue;
            Integer diffNumIx = tables.get(target - nums[i]);
            if (diffNumIx != null) {
                // int curr = nums[i];
                // int diffNum = target - nums[i];
                // int s = curr < diffNum ? curr : diffNum;
                // int b = s == curr ? diffNum : curr;
                ans.add(new int[]{nums[i], target - nums[i]});
                mark.add(nums[i]);
                mark.add(target - nums[i]);
            }
            tables.put(nums[i], i);
        }
        return ans;
    }
}

//leetcode submit region end(Prohibit modification and deletion)

class Test15 {
    public static void main(String[] args) {
        // int[] nums = {-1, 0, 1, 2, -1, -4};
        int[] nums = {0, 0, 0};
        // List<List<Integer>> res = new Solution().threeSum(nums);
        // System.out.println(res);
    }
}